package hash.hashcode;
/**
 * 
 * @Title: CandyHashTable.java 
 * @Package hash.hashcode 
 * @Description: 自定义哈希表
 *               优化哈希表：
 *                  使得哈希表可以进行动态地扩缩容
 *                  哈希表每次扩缩容之后的数组的容量M总为一个素数
 * @author CandyWall   
 * @date 2021年1月12日 下午7:00:40 
 * @version V1.0
 */

import java.util.TreeMap;

public class CandyHashTable_v3<K, V> {
    private TreeMap<K, V>[] hashTable;
    private int M;      // 哈希表容量
    private int size;   // 存储元素的个数
    // 平均每个地址发生哈希冲突的元素个数的上界
    private static final int AVERAGE_HASH_CONFLICT_ELEMENTS_COUNT_UPPER = 10;
    // 平均每个地址发生哈希冲突的元素个数的下界
    private static final int AVERAGE_HASH_CONFLICT_ELEMENTS_COUNT_LOWER = 2;
    // 初始哈希表容量
    private static final int initCapacity = 7;
    // Integer所能表示的最大的数的范围内素数，每两个相邻的数之间差不多两倍关系
    private static final int[] capacityTable = {53, 97, 179, 331, 599, 1087, 
                1973, 3557, 6421, 11579, 20849, 37529, 67559, 121607, 218923, 
                394063, 709321, 1276817, 2298293, 4136939, 7446557, 13403813, 
                24126871, 43428373, 78171091, 140708027, 253274467, 455894071, 
                820609337, 1477096847};
    private int capacityIndex = 0;
    public CandyHashTable_v3(int M) {
        this.M = M;
        hashTable = new TreeMap[M];
        for(int i = 0; i < M; i++) {
            hashTable[i] = new TreeMap<>();
        }
        size = 0;
    }
    
    public CandyHashTable_v3() {
        this(capacityTable[0]);
    }
    
    private int hash(K key) {
        //               16进制转2进制 
        // 0x7fffffff ----------------> 01111111 11111111 11111111 11111111
        // 一个整型的数占4个字节，总共是32位，其中最高位是符号位，0表示正数，1表示负数，
        // 让key的hashCode()值与上0x7fffffff可以去掉符号位
        return (key.hashCode() & 0x7fffffff) % M;
    }
    
    public int getSize() {
        return size;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public void add(K key, V value) {
        TreeMap<K, V> map = hashTable[hash(key)];
        if(!map.containsKey(key)) {
            size++;
            if(size >= AVERAGE_HASH_CONFLICT_ELEMENTS_COUNT_UPPER * M && capacityIndex < capacityTable.length - 1) {
                resize(capacityTable[++capacityIndex]);
            }
        }
        map.put(key, value);
    }
    
    // 扩容
    private void resize(int newSize) {
        M = newSize; // hashTable容量翻倍（可用Hash地址翻倍）
        TreeMap<K, V>[] newHashTable = new TreeMap[M];
        for(int i = 0; i < M; i++) {
            newHashTable[i] = new TreeMap<>();
        }
        // 遍历原来的HashTable，取出其中的所有元素，依次存入到新的newHashTable中
        for(int i = 0; i < hashTable.length; i++) {
            for(K key : hashTable[i].keySet()) {
                newHashTable[hash(key)].put(key, hashTable[i].get(key));
            }
        }
        hashTable = newHashTable;
    }

    public V remove(K key) {
        TreeMap<K, V> map = hashTable[hash(key)];
        V ret = null;
        if(map.containsKey(key)) {
            ret = map.remove(key);
            size--;
            if(size <= AVERAGE_HASH_CONFLICT_ELEMENTS_COUNT_LOWER * M && capacityIndex - 1 >= 0) {
                resize(capacityTable[--capacityIndex]);
            }
        }
        return ret;
    }
    
    public void set(K key, V value) {
        TreeMap<K, V> map = hashTable[hash(key)];
        if(!map.containsKey(key)) {
            throw new IllegalArgumentException("key:" + key + " 不存在！");
        }
        map.put(key, value);
    }
    
    public boolean contains(K key) {
        return hashTable[hash(key)].containsKey(key);
    }
    
    public V get(K key) {
        return hashTable[hash(key)].get(key);
    }
    
    public static void main(String[] args) {
        // 计算整型范围内的素数
        // 从53开始，差不多两倍左右才能输出一个
        int basePrime = 53;
        for(int i = basePrime; i < Integer.MAX_VALUE; i++) {
            int j = 2;
            int sqrt = (int) Math.sqrt(i);
            for(; j <= sqrt; j++) {
                if(i % j == 0) {
                   break; 
                }
            }
            if(j > sqrt) {
                if(i * 1.0 / basePrime  - 1.8 > 0.0) {
                    basePrime = i;
                    System.out.print(i + ", ");
                    i = (int) (basePrime * 1.8);
                }
            }
        }
    }
}
